package org.example.game.history;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/07/07 10:37
 */
public class Solution100328 {

    public static void main(String[] args) {
        List<String> res = new Solution100328().validStrings(3);

        for (String re : res) {
            System.out.println(re);
        }
    }

    public List<String> validStrings(int n) {
        List<String> res = new ArrayList<>();
        res.add("0");
        res.add("1");

        List<String> outList = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            outList = new ArrayList<>();
            for (String re : res) {
                if(re.endsWith("0")){
                    outList.add(re + "1");
                }else {
                    outList.add(re + "0");
                    outList.add(re + "1");
                }
            }
            res = outList;
        }

        return res;
    }
}
